#ifndef __ITERATOR_H_
#define __ITERATOR_H_

namespace stl
{

struct input_iterator_tag  {};
struct output_iterator_tag {};
struct forward_iterator_tag       : public input_iterator_tag         {};
struct bidirectional_iterator_tag : public forward_iterator_tag       {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

//traits
template <typename Iterator>
struct iterator_traits
{
    typedef typename Iterator::difference_type difference_type;
    typedef typename Iterator::value_type value_type;
    typedef typename Iterator::pointer pointer;
    typedef typename Iterator::reference reference;
    typedef typename Iterator::iterator_category iterator_category;
};

template <typename T>
struct iterator_traits <T*>
{
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef random_access_iterator_tag iterator_category;
};

template<typename T>
struct iterator_traits<const T*>
{
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef const T* pointer;
    typedef const T& reference;
    typedef random_access_iterator_tag iterator_category;
};

template<typename Category, typename T, typename Distance = ptrdiff_t,
         typename Pointer = T*, typename Reference = T&>
struct iterator
{
    typedef T         value_type;
    typedef Distance  difference_type;
    typedef Pointer   pointer;
    typedef Reference reference;
    typedef Category  iterator_category;
};

template <typename Iterator>
void _advance(Iterator& i,
              typename iterator_traits<Iterator>::difference_type n,
              input_iterator_tag)
{
    for(; n > 0; --n)
        ++i;
}

template <typename Iterator>
void _advance(Iterator& i,
              typename iterator_traits<Iterator>::difference_type n,
              bidirectional_iterator_tag)
{
    if(n >= 0)
    {
        for(; n > 0; --n)
            ++i;
    }
    else
    {
        for(; n < 0; ++n)
            --i;
    }
}

template <typename Iterator>
void _advance(Iterator& i,
              typename iterator_traits<Iterator>::difference_type n,
              random_access_iterator_tag)
{
    i += n;
}

template <typename InputIterator>
void advance(InputIterator& i,
             typename iterator_traits<InputIterator>::difference_type n)
{
    _advance(i, n, typename iterator_traits<InputIterator>::iterator_category());
}

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type
_distance(Iterator first, Iterator last, input_iterator_tag)
{
    typename iterator_traits<Iterator>::difference_type distance(0);
    for(; first != last; ++first)
        ++distance;
    return distance;
}

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type
_distance(Iterator first, Iterator last, random_access_iterator_tag)
{
    typename iterator_traits<Iterator>::difference_type distance(0);
    return last - first;
}

template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
    return _distance(first, last, typename InputIterator::iterator_category());
}

template <typename Iterator>
class reverse_iterator
    : public iterator<typename iterator_traits<Iterator>::iterator_category,
                      typename iterator_traits<Iterator>::value_type,
                      typename iterator_traits<Iterator>::difference_type,
                      typename iterator_traits<Iterator>::pointer,
                      typename iterator_traits<Iterator>::reference>
{
protected:
    Iterator current;
public:
    typedef Iterator                                            iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type difference_type;
    typedef typename iterator_traits<Iterator>::reference       reference;
    typedef typename iterator_traits<Iterator>::pointer         pointer;

    reverse_iterator() : current(){}
    explicit reverse_iterator(Iterator x) : current(x) {}
    template <typename U> reverse_iterator(const reverse_iterator<U>& u) 
    {
        current = u.base();
    }
    Iterator base() {return current;} const
    reference operator*() {return *current;} const
    pointer   operator->() {return &operator*();} const
    reverse_iterator& operator++() 
    { 
        --current; 
        return *this;
    }

    reverse_iterator  operator++(int)
    {
        auto temp = *this;
        operator++();
        return temp;
    }

    reverse_iterator& operator--() { ++current; return *this; }
    reverse_iterator  operator--(int)
    {
        auto temp = *this;
        operator--();
        return temp;
    }
    reverse_iterator  operator+ (difference_type n) const
    {
        return reverse_iterator(current - n);
    }

    reverse_iterator& operator+=(difference_type n)
    {
        current -= n;
        return *this;
    }
    reverse_iterator  operator- (difference_type n) const
    {
        return reverse_iterator(current + n);
    }
    reverse_iterator& operator-=(difference_type n)
    {
        current += n;
        return *this;
    }

    reference         operator[](difference_type n) const
    {
        return *(current + n);
    }
};

template <typename Iterator1, typename Iterator2>
bool
operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return x.base() == y.base();
}

template <typename Iterator1, typename Iterator2>
bool
operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return x.base() > y.base(); 
}

template <typename Iterator1, typename Iterator2>
bool
operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return !(x == y);
}

template <typename Iterator1, typename Iterator2>
bool
operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return x.base() < y.base();
}

template <typename Iterator1, typename Iterator2>
bool
operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return x.base() <= y.base();
}

template <typename Iterator1, typename Iterator2>
bool
operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return x.base() >= y.base();
}

template <typename Iterator1, typename Iterator2>
typename reverse_iterator<Iterator1>::difference_type
operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
{
    return y.base() - x.base();
}

template <typename Iterator>
reverse_iterator<Iterator>
operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x)
{
    return reverse_iterator(x.base() - n);
}

}   // End of namespace stl

#endif